Masala #0748

Dasturlash musobaqasi bilan shug’ullanib yurgan barchaga Prefiks funksiya nima ekanligi ma’lum bo’lsa kerak. Agar bilmasangiz Prefiks funksiya haqida https://e-maxx.ru/algo/prefix_function havoladan o’rganib olishingiz mumkin.

Keling endi asosiy masalaga o’tamiz!

$S$ to’plam $m$ ta harfli alifbodan tuzilgan uzunligi $n$ ga teng bo’lgan barcha satrlar to’plami.

$F(s)$ funksiyasi $\text{prefix\_function}(s)$ dan olingan to’plamning eng katta qiymati bo’lsin.

Sizning vazifangiz $\sum_{s∈S}F(s)$ ni $X$ ga bo’lgandagi qoldiqni hisoblashdan iborat.

Kirish faylining yagona satrida uchta butun son, $n (1 \le n \le 22)$, $m (1 \le m \le 10^9)$ va $X (1 \le X \le 10^9)$ sonlari kiritiladi.

Chiqish faylida yagona butun son,   $\sum_{s∈S}F(s)$ ni $X$ ga bo’lgandagi qoldiqni chop eting!